This invention pertains generally to the field of digital printing systems, and specifically to a system and process of printing or otherwise displaying complex images using compact representations of trapezoidal image elements.
Conventional digital printing systems receive data corresponding to text and graphics in a variety of formats. These systems process such data to create a set of dots (or "pixels") on a page, which are perceived by a human observer as an image. It is conventional for such systems to represent image information in the memory of the printing system by setting a particular bit in the memory to be on or off depending upon whether a corresponding pixel is to be displayed as black or white. This is called a "bit map" or "pixel map" representation. In color systems, separate memory areas correspond to component colors. Typical computer video display systems similarly rely on pixel-based representations of images.
A conventional technique for processing images is to incorporate a microprocessor into a printing device, and to program the microprocessor to interpret commands from an attached computer in accordance with the protocols of a page description language. Such subsystems are commonly known as "interpreters", and translate the printing commands from the attached computer into commands and data more easily processed by the printing device.
In practice, it is common for interpreters to decompose high-level commands corresponding to complex images into low-level commands representing, for instance, a collection of contiguous trapezoids and other "graphic primitives". For purposes herein, a trapezoid is defined as a closed plane figure bounded by two parallel straight line segments and two additional non-intersecting line segments, each of the additional line segments connecting an endpoint of one of the parallel line segments with an endpoint of the other parallel line segment. Typically, the trapezoids that interpreters produce in the decomposition process have horizontal parallel sides. For example, U.S. Pat. Nos. 5,133,049 and 5,129,051 teach techniques for decomposing an arbitrary polygon into trapezoids for more efficient processing.
Two system architectures are commonly used in the industry for further processing of the low-level commands produced by page description language interpreters. The first, known as a "frame buffer", represents every pixel on a printed page as a separate bit or, in the case of color, as a set of bits in random access memory (RAM). Under this system, any page that can be described as a map of pixels can be printed. Frame buffer systems typically must process the information to be displayed on a frame-by-frame basis in which each frame must be rasterized and the data therein sent serially to the print engine. Furthermore, a substantial amount of frame buffer RAM is required to store information for the page, even when the image to be printed is extremely simple.
The second common architecture, known as "banding", stores all of the graphic primitives to be printed on the page, such as characters, graphics, images, and the like, in one or more display lists stored in the RAM of the printing system. Each display list stores the graphic primitives for one area of the page, typically a horizontal band. Each display list is rasterized in turn into one of a small number of band bit maps, or buffers, the contents of which are sent in turn to the print engine. The band buffers are reused during the processing of all the display lists of the page. Typically, most of the rasterization into band bit maps occurs after the print engine has started to print the page. In the typical laser printer, the engine cannot be stopped in the middle of a page, so this rasterization must be fast enough to keep up with the print engine. In banding systems, relatively little RAM is required to print simple pages, and processing of one page while another page is printing is possible. However, for very complex images the size of the lists can exceed the RAM size of a comparable frame buffer system. Sufficient RAM for handling such complex images must be provided or an error will result. The requirement of real time rasterization of bands is often difficult to achieve, and an error will result if a band fails to rasterize by the time it is called for. The addition of RAM to banding systems can allow them to be converted to frame buffer systems when required.
One contributing factor to the cost and complexity of banding systems is that display list entries can quickly accumulate to an unmanageable size, not only eliminating the primary advantage of this technique but also giving rise to the possibility that not enough RAM will be available to store all of the desired display list entries. For instance, large numbers of trapezoids are created by conventional techniques, such as those taught in the U.S. patents mentioned above, and each must be stored in a display list.
In one conventional system, the representation of a trapezoid includes a set of fixed- or floating-point real-valued coordinates, in a predetermined coordinate system, for each of the four vertices of the trapezoid. In another conventional system, the representation of a trapezoid includes a set of real-valued coordinates for each of the top two vertices (assuming a trapezoid with parallel sides that are horizontal), the real-valued height of the trapezoid, and a real-valued slope for each of the non-horizontal sides of the trapezoid.
To obtain sufficient accuracy in representing the trapezoid, all of these values in the conventional systems are stored in a fixed- or floating-point mathematical format to represent a real value. Representation of such real values is extremely memory-intensive compared to storing integer values, and the conversion of real-valued display list entries into the pixel-based representations needed for printing requires a significant amount of processing time.
Thus, for complex images that are decomposed into a large number of trapezoids, the representations of such trapezoids can consume a large amount of display list memory and take a long time to process at the critical point when display list entries are rendered into band bit maps. It would be desirable to have a system and process for storing representations of such trapezoids as display list entries that are more compact and faster to process than those produced using conventional techniques.